package com.lw.leetcode.hash.a;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * LCP 07. 传递信息
 *
 * @Author liw
 * @Date 2021/7/1 10:24
 * @Version 1.0
 */
public class NumWays {

    public static void main(String[] args) {
        NumWays test = new NumWays();
        int[][] arr = {{0, 2}, {2, 1}, {3, 4}, {2, 3}, {1, 4}, {2, 0}, {0, 4}};
        int k = 3;
        int i = test.numWays(5, arr, k);
        System.out.println(i);
    }

    public int numWays(int n, int[][] relation, int k) {
        n--;
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int[] ints : relation) {
            map.merge(ints[0], new ArrayList<Integer>() {{
                add(ints[1]);
            }}, (a, b) -> {
                a.add(ints[1]);
                return a;
            });
        }
        int i = 1;
        List<Integer> b = new ArrayList<>();
        List<Integer> a = new ArrayList<>(map.get(0));
        while (i < k) {
            for (Integer value : a) {
                List<Integer> integers = map.get(value);
                if (integers != null) {
                    b.addAll(integers);
                }
            }
            i++;
            a = b;
            b = new ArrayList<>();
        }
        int count = 0;
        for (Integer value : a) {
            if (value == n) {
                count++;
            }
        }
        return count;
    }

}
